'''
https://leetcode.cn/problems/handshakes-that-dont-cross
'''

class Solution:
    def numberOfWays(self, num_people: int) -> int:
        MOD = 10 ** 9 + 7
        n = num_people
        dp = [0 for _ in range(n + 1)]
        dp[0] = 1
        for i in range(2, n + 1, 2):
            for j in range(0, i - 1, 2):
                dp[i] += dp[j] * dp[i - j - 2]
                dp[i] %= MOD

        return dp[n]
    def countLetters(self, s: str) -> int:
        n = len(s)